# include <iostream>
# include <vector>
# include <array>
# include <algorithm>
using namespace std;

//// 0表示空子，1表示白，2表示黑

//// 输赢判断函数，返回0表示无结果，1表示白赢，2表示黑赢
int win_lose_judge(int (*chess_state)[15], int color) {
    for (int i = 0; i < 15; i++) {
        for (int j = 0; j < 15; j++) {
            if (chess_state[i][j] == color) {
                vector<array<int, 2>> possible_directions;
                // 检测可能的方向，若在该方向上5个子相同，返回对应颜色胜利，否则返回0
                if (j >= 4) possible_directions.push_back({0, -1});
                if (j >= 4 && i <= 10) possible_directions.push_back({1, -1});
                if (i <= 10) possible_directions.push_back({1, 0});
                if (i <= 10 && j <= 10) possible_directions.push_back({1, 1});
                if (j  <= 10) possible_directions.push_back({0, 1});
                if (i >= 4 && j <= 10) possible_directions.push_back({-1, 1});
                if (i >= 4) possible_directions.push_back({-1, 0});
                if (i >= 4 && j >= 4) possible_directions.push_back({-1, -1});
                for (auto& direct : possible_directions) {
                    int x = direct[0];
                    int y = direct[1];
                    if (chess_state[i][j] == chess_state[i + x][j + y] &&
                        chess_state[i + x][j + y] == chess_state[i + 2 * x][j + 2 * y] &&
                        chess_state[i + 2 * x][j + 2 * y] == chess_state[i + 3 * x][j + 3 * y] &&
                        chess_state[i + 3 * x][j + 3 * y] == chess_state[i + 4 * x][j + 4 * y]) {
                        return color;
                    }
                }
            }
        }
    }
    return 0;
}

// 在命令行中输出棋盘
void display_board(int (*chess_state)[15]) {
    cout << "  ";
    for (int i = 0; i < 15; i++) {
        if (i < 10) cout << i << "  ";
        else cout << i << " ";
    }
    cout << endl;
    for (int i = 0; i < 15; i++) {
        if (i < 10) {
            cout << " ";
        }
        cout << i;
        for (int j = 0; j < 15; j++) {
            if (chess_state[i][j] == 0) {
                cout << "+";
            }
            else if (chess_state[i][j] == 1) {
                cout << "A";
            }
            else {
                cout << "B";
            }
            if (j < 14) cout << "--";
        }
        cout << endl;
    }
}


int single_5_group_evaluate(const int (*group5)) {
    // 评分标准对单个五元组作用。
    bool has_white = false;
    bool has_black = false;
    for (int i = 0; i < 5; i++) {
        if (group5[i] == 1) {
            has_white = true;
        }
        if (group5[i] == 2) {
            has_black = true;
        }
    }
    if ((has_black && has_white) || ((! has_black) && (! has_white))) return 0;
    else if ((! has_black) && has_white) {
        if (group5[0] == 0 && group5[1] == 1 && group5[2] == 1 && group5[3] == 1 && group5[4] == 0) return -2000;
        else {
            // 根据一些文献说相加比逻辑表达式求值要快
            switch (group5[0] + group5[1] + group5[2] + group5[3] + group5[4]) {
                case 1:
                    return -1;
                case 2:
                    return -10;
                case 3:
                    return -1000;
                case 4:
                    return -100000;
                case 5:
                    return -100000000;
                default:
                    return 0;
            }
        }
    }
    else {
        switch (group5[0] + group5[1] + group5[2] + group5[3] + group5[4]) {
            case 2:
                return 1;
            case 4:
                return 10;
            case 6:
                return 100;
            case 8:
                return 1000;
            case 10:
                return 1000000;
            default:
                return 0;
        }
    }
}


int evaluate(int (*board)[15]) {
    // 识别每个五元组，并把所有五元组的值相加
    int total_count = 0;
    // 横向五元组
    for (int i = 0; i < 11; i++) {
        for (int j = 0; j < 15; j++) {
            int group[5] = {0};
            for (int k = 0; k < 5; k++) {
                group[k] = board[i + k][j];
            }
            total_count = total_count + single_5_group_evaluate(group);
        }
    }
    // 竖向五元组
    for (int i = 0; i < 15; i++) {
        for (int j = 0; j < 11; j++) {
            int group[5] = {0};
            for (int k = 0; k < 5; k++) {
                group[k] = board[i][k + j];
            }
            total_count = total_count + single_5_group_evaluate(group);
        }
    }
    // 右斜五元组
    for (int i = 0; i < 11; i++) {
        for (int j = 0; j < 11; j++) {
            int group[5] = {0};
            for (int k = 0; k < 5; k++) {
                group[k] = board[i + k][j + k];
            }
            total_count = total_count + single_5_group_evaluate(group);
        }
    }
    // 左斜五元组
    for (int i = 4; i < 15; i++) {
        for (int j = 0; j < 11; j++) {
            int group[5] = {0};
            for (int k = 0; k < 5; k++) {
                group[k] = board[i - k][j + k];
            }
            total_count = total_count + single_5_group_evaluate(group);
        }
    }
    return total_count;
}


class Node {
public:
    int depth{};
    int value{};
    Node* father{};
    vector<Node*> children;
    int (* root_board)[15]{};
    // 存放新放置的点，array的前两个为x,y坐标，最后一个为颜色。
    vector<array<int, 3>> new_points;
    int has_won{};
    bool evaluated{};
    // 如果没有判断节点是否被求值，那么在一个节点向上更新时，其他未求值节点的默认值可能会比已求值的节点大，从而使求值失效。

    bool is_max_node() const;
    void node_evaluate();
    int board_identify();
    void set(int node_depth, Node* node_father, int (*node_root_board)[15], vector<array<int, 3>> new_pos);
    ~Node();
};

Node::~Node() = default;

bool Node::is_max_node() const {
    if (depth % 2 == 0) {
        return true;
    }
    else {
        return false;
    }
}

void Node::node_evaluate() {
    if (is_max_node() && has_won == 1) value = - 100000000;
    else if ((!is_max_node()) && has_won == 2) value = 10000000;
    else {
        int now_board[15][15] = {0};
        for (int i = 0; i < 15; i++) {
            for (int j = 0; j < 15; j++) {
                now_board[i][j] = root_board[i][j];
            }
        }
        for (auto position : new_points) {
            now_board[position[0]][position[1]] = position[2];
        }
        value = evaluate(now_board);
    }
    evaluated = true;
}

int Node::board_identify() {
    int now_board[15][15] = {0};
    for (int i = 0; i < 15; i++) {
        for (int j = 0; j < 15; j++) {
            now_board[i][j] = root_board[i][j];
        }
    }
    for (auto position : new_points) {
        now_board[position[0]][position[1]] = position[2];
    }
    if (is_max_node()) return win_lose_judge(now_board, 1);
    else return win_lose_judge(now_board, 2);
}

void Node::set(int node_depth, Node* node_father, int (*node_root_board)[15], vector<array<int, 3>> node_new_pos) {
    depth = node_depth;
    father = node_father;
    root_board = node_root_board;
    new_points = std::move(node_new_pos);
    // node_new_pos被移入节点，node_new_pos自己变空，所以需要在扩展节点的时候先copy父节点的新节点，加入可能的节点后移动到子节点内。
    has_won = board_identify();
    children.clear();
    value = 0;
    evaluated = false;
}


class GameTree {
public:
    int radius{};
    int max_depth{};
    Node* root_node{};
    Node* next_node{};
    vector<Node*> non_expand_nodes;
    vector<Node*> expanded_nodes;
    int now_board[15][15]{}; // 已优化，仅在树中存储棋盘布局

    array<int, 2> set_next_pos();
    bool is_alpha_beta_cut(Node* node);
    void expand_children_nodes(Node* node);
    vector<array<int, 2>> search_nodes(Node* node) const;
    void update_value_from_node(Node* node);
    array<int, 2> game();
    void set(int expand_radius, int tree_max_depth, int (*root_board)[15]);
    ~GameTree();
};

void GameTree::set(int expand_radius, int tree_max_depth, int (*root_board)[15]) {
    radius = expand_radius;
    max_depth = tree_max_depth;
    for (int i = 0; i < 15; i++) {
        for (int j = 0; j < 15; j++) {
            now_board[i][j] = root_board[i][j];
        }
    }
    vector<array<int, 3>> root_no_new_positions{};
    root_node = new Node();
    next_node = new Node();
    root_node->set(0, nullptr, now_board, root_no_new_positions);
    non_expand_nodes.clear();
    expanded_nodes.clear();
}

array<int, 2> GameTree::set_next_pos() {
    if (! root_node->children.empty()) {
        for (auto& child_node : root_node->children) {
            if (child_node->evaluated) {
                next_node = child_node;
                break;
            }
        }
        for (auto& n : root_node->children) {
            if (n->value > next_node->value && n->evaluated) {
                next_node = n;
            }
        }
        array<int, 2> res{};
        for (int i = 0; i < 2; i++) res[i] = next_node->new_points[0][i];
        return res;
    }
    else return {-1, -1};
}

bool GameTree::is_alpha_beta_cut(Node* node) {
    if (node == nullptr || node->father == nullptr) return false;
    if (node->is_max_node() && node->value > node->father->value) return true;
    if ((! node->is_max_node()) && node->value < node->father->value) return true;
    return is_alpha_beta_cut(node->father);
}

vector<array<int, 2>> GameTree::search_nodes(Node *node) const {
    int board_judge[15][15] = {0};
    vector<array<int, 2>> new_positions;
    int board[15][15] = {0};
    for (int i = 0; i < 15; i++) {
        for (int j = 0; j < 15; j++) {
            board[i][j] = node->root_board[i][j];
        }
    }
    for (auto & position : node->new_points) board[position[0]][position[1]] = position[2];
    for (int i = 0; i < 15; i++) {
        for (int j = 0; j < 15; j++) {
            if (board[i][j] != 0) {
                board_judge[i][j] = 1;
            }
        }
    }
    for (int i = 0; i < 15; i++) {
        for (int j = 0; j < 15; j++) {
            if (board_judge[i][j] == 0) {
                bool decided = false;
                for (int m = max(i - radius, 0); m < min(i + radius + 1, 15); m++) {
                    for (int n = max(j - radius, 0); n < min(j + radius + 1, 15); n++) {
                        if (board_judge[m][n] == 1) {
                            new_positions.push_back({i, j});
                            board_judge[i][j] = 2;
                            decided = true;
                        }
                        if (decided) break;
                    }
                    if (decided) break;
                }
            }
        }
    }
    return new_positions;
}

void GameTree::expand_children_nodes(Node *node) {
    vector<array<int, 2>> new_positions = search_nodes(node);
    vector<array<int, 3>> new_positions_in_child{};
    for (auto& position : new_positions) {
        new_positions_in_child = node->new_points;
        if (node->depth % 2 == 0) new_positions_in_child.push_back({position[0], position[1], 2}); //possible_board[position[0]][position[1]] = 2;
        else new_positions_in_child.push_back({position[0], position[1], 1});
        Node* new_node = new Node();
        new_node->set(node->depth + 1, node, node->root_board, new_positions_in_child);
        node->children.push_back(new_node);
        non_expand_nodes.insert(non_expand_nodes.begin(), new_node);
    }
}

void GameTree::update_value_from_node(Node *node) {
    if (node == nullptr) {
        return;
    }
    if (node->children.empty()) {
        update_value_from_node(node->father);
    }
    else {
        if (node->is_max_node()) {
            int largest_value = 0;
            for (auto& child_node : node->children) {
                if (child_node->evaluated) {
                    largest_value = child_node->value;
                    break;
                }
            }
            for (auto& child_node : node->children) {
                if (child_node->value > largest_value && child_node->evaluated) {
                    largest_value = child_node->value;
                }
            }
            if (! node->evaluated) {
                node->value = largest_value;
                node->evaluated = true;
            }
            else if (largest_value > node->value && node->evaluated) {
                node->value = largest_value;
                update_value_from_node(node->father);
            }
        }
        if (! node->is_max_node()) {
            int smallest_value = 0;
            // 要把求最大或者最小的初始值接到被赋值的节点上，否则会因为节点初始设置而错误。
            for (auto& child_node : node->children) {
                if (child_node->evaluated) {
                    smallest_value = child_node->value;
                    break;
                }
            }
            for (auto& child_node : node->children) {
                if (smallest_value > child_node->value && child_node->evaluated) {
                    smallest_value = child_node->value;
                }
            }
            if (! node->evaluated) {
                node->value = smallest_value;
                node->evaluated = true;
            }
            else if (smallest_value < node->value && node->evaluated) {
                node->value = smallest_value;
                update_value_from_node(node->father);
            }
        }
    }
}

array<int, 2> GameTree::game() {
    non_expand_nodes.push_back(root_node);
    while (! non_expand_nodes.empty()) {
        Node* node = non_expand_nodes[0];
        non_expand_nodes.erase(non_expand_nodes.begin());
        expanded_nodes.push_back(node);
        if (is_alpha_beta_cut(node->father)) continue;
        if (node->depth < max_depth && node->has_won == 0) {
            // 仅在深度不够和没有分出胜负的棋局上扩展节点
            expand_children_nodes(node);
            if (! node->children.empty()) continue;
        }
        node->node_evaluate();
        update_value_from_node(node);
    }
    return set_next_pos();
}

GameTree::~GameTree() {
    for (auto & node : expanded_nodes) {
        delete node;
    }
}


int main() {
    // 对博弈树的定义
    int max_depth = 3; // 内存已优化，目前这个参数是兼顾速度和博弈能力的，如果深度太大，计算太慢，扩展范围太大，棋力下降。
    int radius = 2;

    char game_start;
    cout << "game start?" << endl;
    cin >> game_start;
    int board[15][15] = {0};
    while (game_start == 'y') {
        display_board(board);
        array<int, 2> new_position{};
        cout << "your turn" << endl;
        cin >> new_position[0] >> new_position[1];
        if (new_position[0] == -1) {
            break;
        }
        else {
            if (board[new_position[0]][new_position[1]] == 0) {
                board[new_position[0]][new_position[1]] = 1;
                int result = win_lose_judge(board, 1);
                if (result == 1) {
                    cout << "you win" << endl;
                    for (auto & i : board) {
                        for (int & j : i) {
                            j = 0;
                        }
                    }
                    continue;
                }
                GameTree gameTree;
                gameTree.set(radius, max_depth, board);
                array<int, 2> machine_new_pos = gameTree.game();
                board[machine_new_pos[0]][machine_new_pos[1]] = 2;
                result = win_lose_judge(board, 2);
                if (result == 2) {
                    cout << "machine wins" << endl;
                    for (auto & i : board) {
                        for (int & j : i) {
                            j = 0;
                        }
                    }
                    continue;
                }
            }
            else {
                cout << "repeated input" << endl;
                continue;
            }
        }
    }
    return 0;
}